1. Field of Invention
This invention is directed to systems and methods for determining if a finite-state automaton or a finite-state transducer is determinizable.
2. Description of Related Art
Finite-state automata and finite-state transducers, whether weighted or unweighted, are used in many fields to represent complex systems. For example, weighted finite-state transducers are used in many recognition applications, such as speech recognition, gesture recognition and multimodal recognition.
Finite-state transducers are also used in speech-to-text and text-to-speech systems to represent various aspects of the recognition and/or conversion process. Finite-state automata and finite-state transducers are classical computational devices that can be used in a large variety of locations. A weighted finite-state automaton is a finite-state automaton in which each transition between two states is labeled with some weight in addition to the usual input symbol. Finite-state transducers are finite-state automata whose transitions are labeled with both input labels and output labels. Thus, weighted finite-state transducers include input labels, output labels and weights. Weighted finite-state automata and weighted finite-state transducers can be used in text processing, speech processing and image processing to account for the variability within the input data and to rank various hypotheses for the correct processing of the data.
Weighted finite-state automata and finite-state transducers are used to provide a common representation for each component of a complex system in many applications. Such weighted finite-state automata and finite-state transducers can use generalized methods for simplifying and/or combining components, such as the composition of two weighted finite-state automata or transducers. A finite-state automaton or transducer is deterministic if that finite-state automaton or transducer has a unique initial state and if no two transitions of the finite-state automaton or transducer leaving the same state have the same input label. The time efficiency of such finite-state automata or transducers is substantially increased when the finite-state automata or transducers that are implemented are deterministic. Additionally, the size, in number of states and/or the number of transitions between states, can be reduced for such deterministic finite-state automata or transducers using generalized minimization methods.
U.S. Pat. No. 6,243,679 to Mohri et al., which is incorporated herein by reference in its entirety, discloses systems and methods for both determinizing and minimizing a finite-state automaton or transducer. That is, the incorporated 679 patent discloses systems for converting a non-deterministic weighted finite-state automaton, such as that shown in FIG. 1, into a deterministic weighted finite-state automaton, such as that shown in FIG. 2. The incorporated 679 patent also discloses systems and methods for minimizing weighted finite-state automata and transducers.
However, unlike unweighted finite-state automata, weighted finite-state automata and finite-state transducers, whether weighted or unweighted, may not be determinizable. While the determinizability of many trivial weighted finite-state automata and finite-state transducers can be determined by inspection or using known techniques for determining the determinizability of such weighted finite-state automata or finite-state transducers, such methods cannot be used with the finite-state transducers or weighted finite-state automata used to represent components of any reasonable complexity.
In particular, the known methods for determining the determinizability of finite-state transducers and weighted finite-state automata have a complexity that is on the order of the sixth power of the number of states within the finite-state transducer or the weighted finite-state automata. Such conventional methods for determining the determinizability of a particular finite-state transducer or weighted finite-state automaton are not guaranteed to return an answer in a reasonable period of time and, for very large finite-state transducers used in speech, gesture, and/or multimodal recognition systems, which may have millions of states, would not have been guaranteed to complete within the current age of the universe.
As a result, rather than attempting to determine if a particular finite-state transducer or weighted finite-state automaton is determinizable, current practice is to attempt to determinize that finite-state transducer or weighted finite-state automaton. Then, if the determinization method does not halt within a reasonable period of time, the non-deterministic finite-state transducer or weighted finite-state automaton being determinized is assumed to be undeterminizable. However, this causes both waste of computer resources expended in attempting to determinize a non-determinizable non-deterministic finite-state transducer or weighted finite-state automaton, as well as unnecessarily abandoning attempts to determinize determinizable non-deterministic finite-state transducers or finite-state automata who nonetheless have not terminated within the reasonable period of time.
In particular, A. Weber et al., “Economy of Description for Single-Valued Transducers,” (Information and Computation, 118(2):327-340, 1995), M-P Beal, et al., “Squaring Transducers: An Efficient Procedure for Deciding Functionality and Sequentiality,” in (Proceedings of LATIN'2000, Lecture Notes in Computer Science, v. 1776, 2000), and A. L. Buchsbaum, et al., “On the Determinization of Weighted Finite Automata,” (SIAM, Journal of Computing, 30(5):1502-1531, 2000), each incorporated herein by reference in its entirety, disclose the various methods that are usable to determine the determinizability of a finite-state transducer or a weighted finite-state automaton. However, all of these methods suffer from the drawbacks outlined above.